梅森素数

性质

本节研究 $a^n-1$ 素数。

通过下表观察可得知：

$a$ 是奇数时， $a^n-1$ 是偶数。所以 $a$ 只能为偶数。

$a^n-1$ 总是被 $a-1$ 整除。
- 证明：几何级数公式（Geometric Series）
  $x^{n}-1=(x-1)\left(x^{n-1}+x^{n-2}+\cdots+x^{2}+x+1\right)$
  展开右边乘法即可证明几何级数。
所以 $a$ 只能为2。

观察下表 $2^n-1$ 的情况：

不是所有 $2^n-1$ 都是素数。

如果 $n$ 被 $m$ 整除，则 $2^n-1$ 被 $2^m-1$ 整除。
- 观察
  如果 $n$ 是偶数， $2^n-1$ 被 $2^2-1=3$ 整除。
  如果 $n$ 被3整除， $2^n-1$ 被 $2^3-1=7$ 整除。
  如果 $n$ 被5整除， $2^n-1$ 被 $2^5-1=31$ 整除。
- 证明：同样利用几何级数公式， $2^n=(2^{m})^k$
  $2^{n}-1=\left(2^{m}\right)^{k}-1=\left(2^{m}-1\right)\left(\left(2^{m}\right)^{k-1}+\left(2^{m}\right)^{k-2}+\cdots+\left(2^{m}\right)^{2}+\left(2^{m}\right)+1\right)$
所以 $n$ 一定是素数。

命题1. 如果整数 $a\ge2$ 与 $n\ge2$ ，如果 $a^n-1$ 是素数，则 $a$ 一定等于2且 $n$ 一定是素数。

Proposition 1. If $a^n-1$ is prime for some numbers $a\ge2$ and $n\ge2$ , then a must equal 2 and n must be a prime.

不是所有的 $2^p-1$ 都是素数。

应用

在密码学中，有限域中的运算性能极大影响密码协议的实现。在这些运算中，逆运算是最复杂的，模运算、乘法次之。

如果有限域选择梅森素数，得益于它的优良性质，可以极大提高运算效率，特别是有限域下的模运算、乘法操作。

Modular Reduction

根据性质： $2^p \equiv 1 \pmod{2^p-1}$

可得： $x=a\cdot 2^p +b\equiv a+b \pmod{2^p-1}$

如果将 $x$ 写作比特形式，模运算约减为将高位比特串和低位比特串相加。

C++伪代码实现（以 $p=2^{61}-1$ 为例）：

代码

#define MERSENNE_PRIME_EXP 61
const uint64_t PR = 2305843009213693951; //2^61-1
uint64_t mod(uint64_t x)
{
    uint64_t i = (x & PR) + (x >> MERSENNE_PRIME_EXP);
    return (i>=p) ? i - p: i;
}

Multiplication

以 $p=2^{61}-1$ 为例， $a$ 和 $b$ 相乘后，得到一个最多122-bit的数字，用同样的方法，将高位比特和低位比特相加。（如果结果更长，就按段一直叠加）

在实现上可以使用64-bit乘法优化(可以用指令集加速)：

代码

/**
 * @brief 64-bit multiplication
 * 
 * @param a 
 * @param b 
 * @param c [out]pointer to hign 64-bit
 * @return uint64_t [out]low 64-bit
 */
#if defined(__x86_64__) && defined(__BMI2__)
inline uint64_t mul64(uint64_t a, uint64_t b, uint64_t *c)
{
    return _mulx_u64((unsigned long long)a, (unsigned long long)b, (unsigned long long*)c);
}
#else
inline uint64_t mul64(uint64_t a, uint64_t b, uint64_t *c)
{
    __uint128_t aa = a;
    __uint128_t bb = b;
    auto cc = aa*bb;
		// c is a pointer to high 64-bit
    *c = cc>>64;
		// return low 64-bit
    return (uint64_t)cc;
}
#endif

inline uint64_t mult_mod(uint64_t a, uint64_t b)
{
    uint64_t c = 0;
    uint64_t e = mul64(a, b, (uint64_t*)&c);
    // c is hign 64-bit
    // e is low 64-bit
    uint64_t ret = (e & PR) + ( (e>>MERSENNE_PRIME_EXP) ^ (c<< (64-MERSENNE_PRIME_EXP)));
    return (ret >= PR) ? (ret-PR) : ret;
}

Reference

数论概论（原书第4版本） A Friendly Introduction to Number Theory.

代码参考于emp-zk.